在分散的优化环境中,$ n $优化节点网络中的每个代理$ i $都具有私有函数$ f_i $,而节点与邻居进行通信以合作最大程度地减少聚合目标$ \ sum_ {i = 1}^n f_i $。在这种情况下,同步节点的更新会影响大量的沟通开销和计算成本,因此,最近的许多文献都集中在异步优化算法的分析和设计上,其中代理在任意时间激活和通信而无需不需要全球同步执行器。尽管如此,在大多数关于该主题的工作中,活动节点选择一个基于固定概率(例如,随机均匀)接触的邻居,这种选择忽略了在激活时忽略优化景观。取而代之的是,在这项工作中,我们介绍了一项优化感知的选择规则,该规则选择具有最高双重成本提高的邻居(与手头问题的基于共识的双重化有关的数量)。该方案与用于坐标更新的高斯 - 南威尔(GS)规则的坐标下降(CD)方法有关;但是,在我们的环境中,在每次迭代时只能访问一部分坐标(因为每个节点都只能与其直接邻居进行通信),因此有关GS方法的现有文献不适用。为了克服这一难度,我们开发了一个新的分析框架,用于平稳且强烈凸出$ f_i $,该框架涵盖了设定的CD算法类 - 该类直接适用于分散的场景,但不限于它们 - 我们 - 我们表明所提出的固定GS规则在网络中达到最高度的速度(在高度连接的图中为$ \ theta(n)$的速度)。随后在使用合成数据的数值实验中验证了我们的理论分析预测的加速。
translated by 谷歌翻译
在许多在线决策过程中,要求优化代理在具有许多固有相似之处的大量替代方案之间进行选择。反过来,这些相似性意味着可能会混淆标准离散选择模型和匪徒算法的损失。我们在嵌套土匪的背景下研究了这个问题,这是一类对抗性的多臂匪徒问题,学习者试图在存在大量不同的替代方案的情况下最小化他们的遗憾,并具有嵌入式(非组合)相似性的层次结构。在这种情况下,基于指数级的蓝图(例如树篱,EXP3及其变体)的最佳算法可能会产生巨大的遗憾,因为它们倾向于花费过多的时间来探索与相似,次优成本的无关紧要的替代方案。为此,我们提出了一种嵌套的指数权重(新)算法,该算法根据嵌套的,分步选择方法对学习者的替代方案进行分层探索。这样一来,我们就获得了一系列紧密的界限,以表明学习者可以有效地解决与替代方案之间高度相似性的在线学习问题,而不会发生红色的巴士 /蓝色巴士悖论。
translated by 谷歌翻译
许多重要的学习算法,例如随机梯度方法,通常被部署以解决Riemannian歧管上的非线性问题。在这些应用中,我们提出了一个概括和扩展Robbins和Monro的精确随机近似框架的Riemannian算法家族。与他们的欧几里得对应物相比,由于歧管上缺乏全局线性结构,Riemannian迭代算法的理解要少得多。我们通过引入扩展的费米坐标框架来克服这一困难,该框架使我们能够绘制拟议的Riemannian Robbins-Monro(RRM)算法类别的渐近行为,以在基础歧管上非常轻微的假设下,在相关的确定性动力学系统下的算法。这样一来,我们提供了一个几乎肯定的收敛结果的一般模板,该模板镜像并扩展了欧几里得robbins-Monro方案的现有理论,尽管其分析要大得多,需要大量的新几何成分。我们通过使用该框架来建立基于回缩的类似物的融合来展示提出的RRM框架的灵活性,以解决最小化问题和游戏的流行乐观 /额外梯度方法,并且我们为其收敛提供了统一的处理。
translated by 谷歌翻译
当学习者与其他优化代理进行连续游戏时,我们研究了遗憾最小化的问题:在这种情况下,如果所有玩家都遵循一种无重组算法,则相对于完全对手环境,可能会达到较低的遗憾。我们在变异稳定的游戏(包括所有凸孔和单调游戏的连续游戏)的背景下研究了这个问题,当玩家只能访问其个人回报梯度时。如果噪音是加性的,那么游戏理论和纯粹的对抗性设置也会获得类似的遗憾保证。但是,如果噪声是乘法的,我们表明学习者实际上可以持续遗憾。我们通过学习速率分离的乐观梯度方案实现了更快的速度 - 也就是说,该方法的外推和更新步骤被调整为不同的时间表,具体取决于噪声配置文件。随后,为了消除对精致的超参数调整的需求,我们提出了一种完全自适应的方法,可以在最坏的和最佳案例的遗憾保证之间平稳地插入。
translated by 谷歌翻译
我们开发了一个统一的随机近似框架,用于分析游戏中多学院在线学习的长期行为。我们的框架基于“原始偶尔”,镜像的Robbins-Monro(MRM)模板,该模板涵盖了各种各样的流行游戏理论学习算法(梯度方法,乐观的变体,Exp3算法,用于基于付费的反馈,在有限游戏等中)。除了提供这些算法的综合视图外,提出的MRM蓝图还使我们能够在连续和有限的游戏中获得渐近和有限时间的广泛新收敛结果。
translated by 谷歌翻译
使用隔室模型的多种方法已被用于研究Covid-19的大流行,并且使用这些模型的机器学习方法的使用取得了特别明显的成功。我们在这里提出了一种使用“物理知情的神经网络”(PINN)的变体来分析Covid-19美国开发的可访问数据的方法,该方法能够使用模型的知识来帮助学习。我们说明了使用标准PINN方法的挑战,然后如何对网络进行适当和新颖的修改,即使在我们的信息不完整的情况下,网络也可以表现出色。还评估了模型参数的可识别性方面,以及使用小波变换来降低可用数据的方法。最后,我们讨论了神经网络方法与不同参数值模型合作的能力,以及在估计人群中如何有效测试案例的具体应用,从而通过各自提供了美国州的排名测试。
translated by 谷歌翻译